1. Field of the Invention
The present invention relates to a decoding system for decoding an error correction code such as an extended Reed-Solomon code extended by one symbol. More particularly, the invention relates to a decoding system which enables a mixed correction of, for example, a one-extended Reed-Solomon code at one path by integration of means for performing normal correction and erasure correction of an extended symbol.
2. Description of the Related Art
First, an error correction system will be described with reference to FIG. 1.
Let us consider a case where the number of added parity symbols is p and information I=(I0, I1, . . . , Ikxe2x88x921) of k symbols is transmitted. The information of k symbols is encoded by an encoder (encoding block) so that p parity symbols are added and a code word C=(C0, C1, . . . , Cnxe2x88x921) with a length of n=k+p is obtained.
The code word passes through a transmission path with an error and is received as a received word R=(R0, R1, . . . , Rnxe2x88x921) including an error. When an i-th error is made ei, Ri=Ci+ei. The received word R is decoded by a decoder (decoding block), so that a presumed code word Cp=(Cp0, Cp1, . . . , Cpnxe2x88x921) is obtained. Presumed information Ip=(Ip0, Ip1, . . . , Ipkxe2x88x921) is obtained from this code word Cp.
A Reed-Solomon code is one of widely-used error correction codes. In the Reed-Solomon code, when a symbol is expressed by m bits, a maximum code length n max is 2mxe2x88x921. For example, when a symbol is expressed by 8 bits, the maximum code length xe2x80x98n maxxe2x80x99 becomes 255.
There is also a one-extended Reed-Solomon code in which the code length of the Reed-Solomon code is extended by one symbol, and the maximum code length xe2x80x98n maxxe2x80x99 becomes 2m. For example, in the case where a symbol is expressed by 8 bits, the maximum code length xe2x80x98n maxxe2x80x99 becomes 256. In the one-extended Reed-Solomon code, while the number of parity symbols p is kept as it is, the information symbols can be made larger than the Reed-Solomon code by one symbol, namely, k+1 symbols.
Next, a decoding method of the Reed-Solomon code will be described. There are three decoding methods, that is, a normal correction in which decoding is performed from onlya received word R, an erasure correction in which decoding is performedby using a received word R and an erasure flag F=(F0, F1, . . . , Fnxe2x88x921) indicating a position of the received word where an error appears to exist, and a mixed correction where the normal correction and the erasure correction are performed at the same time. Here, with reference to FIGS. 2 to 6, a decoding method of the mixed correction of the most general Reed-Solomon code will be described.
Here, with respect to a primitive polynomial f(x) on a field GF(2)={0, 1}, a root of f(x)=0 is made xcex1, and an extension field of GF(2) is formed. At this time, if the degree of the primitive polynomial f(x) is made m, one symbol becomes m bits, and the extension field GF(2m) is expressed by equation (1).
[Numerical Expression 1]
GF(2m)={0, 1, xcex1, xcex12, . . . xcex1x}, where x=2mxe2x88x922xe2x80x83xe2x80x83(1)
A generating polynomial g(x) of the Reed-Solomon code used here is expressed by equation (2).
[Numerical Expression 2]                              g          ⁡                      (            x            )                          =                              ∏                          i              =              0                                      p              -              1                                ⁢                      xe2x80x83                    ⁢                      (                          x              -                              α                i                                      )                                              (        2        )            
FIG. 2 shows a flowchart of decoding of the Reed-Solomon code.
First, at step 100, a received word R=(R0, R1, . . . , Rnxe2x88x921) and an erasure flag F=(F0, F1, . . . , Fnxe2x88x921) are given. The erasure flag F is a flag in which 1 is set for a position in the received word R where it is predicted that an error exists, and 0 is set for other positions where it is predicted that an error does not exist.
Next, at step 101, the number of erasures xcex5 is obtained through equation (3), and an erasure position polynomial E(x) is obtained through equation (4).
[Numerical Expression 3]
xcex5=#{i|Fi=1} [for i=0xcx9c(nxe2x88x921)]xe2x80x83xe2x80x83(3)
E(x)=ΠFi=1(1xe2x88x92xcex1ix) [for i=0xcx9c(nxe2x88x921)]xe2x80x83xe2x80x83(4)
Next, at step 102, using a parity check matrix H as expressed by equation (5), a syndrome S=(S0, S1, . . . , Spxe2x88x921) is obtained from equation (6). A calculation method of the syndrome S will be described later with reference to FIG. 3. Then a syndrome polynomial S(x) as expressed by equation (7) is obtained.
[Numerical Expression 4]                    H        =                  (                      xe2x80x83                    ⁢                                                    1                                            1                                            1                                            ⋯                                            1                                                                    1                                            α                                                              α                  2                                                            ⋯                                                              α                                      n                    -                    1                                                                                                                        xe2x80x83                                                                              xe2x80x83                                                            ·                                                              xe2x80x83                                                                              xe2x80x83                                                                                                      xe2x80x83                                                                              xe2x80x83                                                            ·                                                              xe2x80x83                                                                              xe2x80x83                                                                                                      xe2x80x83                                                                              xe2x80x83                                                            ·                                                              xe2x80x83                                                                              xe2x80x83                                                                                                      xe2x80x83                                                                              xe2x80x83                                                                              xe2x80x83                                                                              xe2x80x83                                                                              xe2x80x83                                                                                    1                                                              α                                      p                    -                    1                                                                                                α                                      2                    ⁢                                          (                                              p                        -                        1                                            )                                                                                                  ⋯                                                              α                                                            (                                              n                        -                        1                                            )                                        ⁢                                          (                                              p                        -                        1                                            )                                                                                                    ⁢                      xe2x80x83                    )                                    (        5        )            xe2x80x83tS=HtRxe2x80x83xe2x80x83(6)
S(x)=S0+S1x+S2x2+ . . . +Spxe2x88x921xpxe2x88x921xe2x80x83xe2x80x83(7)
Next, at step 103, using the erasure position polynomial E(x) and the syndrome polynomial S(x), a modified syndrome polynomial Sm(x) is obtained as expressed by equation (8).
[Numerical Expression 5]
Sm(x)=S(x)E(x) mod xpxe2x80x83xe2x80x83(8)
Next, at step 104, an error evaluator polynomial xcfx89(x) and an error locator polynomial "sgr"(x) are obtained by using the modified syndrome polynomial Sm(x). A calculation method of the error evaluator polynomial xcfx89(x) and the error locator polynomial "sgr"(x) will be described later with reference to FIG. 4.
Next, at step 105, the condition of deg xcfx89(x) less than deg "sgr"(x) is judged, and if the condition is false, the procedure proceeds to step 110, outputs an error signal, and is ended, and if true, it proceeds to step 106. Here, deg xcfx89(x) is the degree of the error evaluator polynomial xcfx89(x) and deg "sgr"(x) is the degree of the error locator polynomial "sgr"(x).
At step 106, the condition of equation (9) is judged, and if false, the procedure proceeds to step 110, outputs an error signal, and is ended, and if true, it proceeds to step 107. Incidentally, a bracket of the right side of equation (9) means that a decimal fraction is omitted. The same thing can be said to subsequent equations.
[Numerical Expression 6]                              deg          ⁢                      xe2x80x83                    ⁢                      σ            ⁡                          (              x              )                                      ≤                  ⌊                                    p              +              ϵ                        2                    ⌋                                    (        9        )            
At step 107, an error position is detected by using the error locator polynomial "sgr"(x). A calculation method of the error position will be described later with reference to FIG. 5. At step 108, the condition of #roots=deg "sgr"(x) is judged, and if false, the procedure proceeds to step 110, outputs an error signal, and is ended, and if true, it proceeds to step 109. Here, the #roots is the number of error positions detected at step 107.
At step 109, from the error evaluator polynomial xcfx89(x), the error locator polynomial "sgr"(x) obtained at step 104, and the error position i detected at step 107, an error value ei at the position i is calculated. Further, from the received word R, the error position i, and the error value ei, presumed information Ip=(Cp0, Cp1, . . . , Cpkxe2x88x921) is calculated and is outputted. A calculation method of the presumed information Ip will be described later with reference to FIG. 6.
With reference to the flowchart of FIG. 3, a method of calculating the syndrome S from the received word R will be described.
First, at step 120, the received word R=(R0, R1, . . . , Rnxe2x88x921) is received. At step 121, the respective elements (S0, S1, . . . , Spxe2x88x921) of the syndrome S are initialized by the element R0 of the received word R. At step 122, a counter I is initialized to 1.
Next, at step, 123, the respective elements of the syndrome S are renewed by equation (10).
[Numerical Expression 7]
Sj=Sj+Rixc3x97xcex1ij[for j=0 to (pxe2x88x921)]xe2x80x83xe2x80x83(10)
Next, at step 124, the value of the counter i is increased by 1. At step 125, the condition of i less than n is judged, and if true, the procedure returns to step 123 and the syndrome calculation is repeated, and if false, it proceeds to step 126 and outputs the syndrome S=(S0, S1, . . . , Spxe2x88x921).
Using a flowchart of FIG. 4, a method of calculating the error evaluator polynomial xcfx89(x) and the error locator polynomial "sgr"(x) from the modified syndrome polynomial Sm(x) (a method by algorithm using the Euclidean mutual division method) will be described.
First, at step 130, rxe2x88x921(x), r0(x), uxe2x88x921(x), u0(x), vxe2x88x921(x), and v0(x) are initialized as expressed by equation (11).
[Numerical Expression 8]                    {                                                                                                                        r                                              -                        1                                                              ⁡                                          (                      x                      )                                                        =                                      x                    p                                                                                                                                                                  r                      0                                        ⁡                                          (                      x                      )                                                        =                                      Sm                    ⁡                                          (                      x                      )                                                                                                    ⁢                      {                                                                                                                                                        u                                                      -                            1                                                                          ⁡                                                  (                          x                          )                                                                    =                      1                                                                                                                                                                                    u                          0                                                ⁡                                                  (                          x                          )                                                                    =                      0                                                                                  ⁢                              {                                                                                                                                                          v                                                          -                              1                                                                                ⁡                                                      (                            x                            )                                                                          =                        0                                                                                                                                                                                                      v                            0                                                    ⁡                                                      (                            x                            )                                                                          =                        1                                                                                                                                                    (        11        )            
Next, at step 131, the counter i is initialized to 0. At step 132, the value of the counter i is increased by 1. At step 133, division is performed, so that qixe2x88x921(x) satisfying equation (12) is found. Here, deg ri(x) is the degree of ri(x), and deg rixe2x88x921(x) is the degree of rixe2x88x921(x).
[Numerical Expression 9]
ri(x)=rixe2x88x922(x)xe2x88x92qixe2x88x921(x)rixe2x88x921(x), deg ri(x) less than deg rixe2x88x921(x)xe2x80x83xe2x80x83(12)
Next, at step 134, using qixe2x88x921(x) found at step 133, ui(x) and vi(x) are renewed as expressed by equation (13).
[Numerical Expression 10]                    {                                                                                                  u                    i                                    ⁡                                      (                    x                    )                                                  =                                                                            u                                              i                        -                        2                                                              ⁡                                          (                      x                      )                                                        -                                                                                    q                                                  i                          -                          1                                                                    ⁡                                              (                        x                        )                                                              ⁢                                                                  u                                                  i                          -                          1                                                                    ⁡                                              (                        x                        )                                                                                                                                                                                                          v                    i                                    ⁡                                      (                    x                    )                                                  =                                                                            v                                              i                        -                        2                                                              ⁡                                          (                      x                      )                                                        -                                                                                    q                                                  i                          -                          1                                                                    ⁡                                              (                        x                        )                                                              ⁢                                                                  v                                                  i                          -                          1                                                                    ⁡                                              (                        x                        )                                                                                                                                                    (        13        )            
Next, at step 135, the condition (end condition) of equation (14) is judged, and if true, the procedure proceeds to step 136, and if false, it returns to step 132, and division is again performed at step 133. At step 136, as expressed by equation (15), the error evaluator polynomial xcfx89(x) and the error locator polynomial "sgr"(x) are set.
[Numerical Expression 11]                              deg          ⁢                      xe2x80x83                    ⁢                                    r              i                        ⁡                          (              x              )                                       less than                   ⌊                                    p              +              ϵ                        2                    ⌋                                    (        14        )                                {                                                                              ω                  ⁡                                      (                    x                    )                                                  =                                                      r                    i                                    ⁡                                      (                    x                    )                                                                                                                                            σ                  ⁡                                      (                    x                    )                                                  =                                                                            v                      i                                        ⁡                                          (                      x                      )                                                        ·                                      E                    ⁡                                          (                      x                      )                                                                                                                              (        15        )            
By using a flowchart of FIG. 5, a method of detecting an error position from the error locator polynomial "sgr"(x) will be described.
First, at step 140, the counter i is initialized to 0. At step 141, the condition of "sgr"(xcex1xe2x88x921)=0 is judged, and if true, the position indicated by the counter i is an erroneous position, and the procedure proceeds to step 142, and if false, the position indicated by the counter i is not an erroneous position, and. the procedure proceeds to step 143. At step 142, the value of the counter i expressing the detected error position is stored into memory A, and the procedure proceeds to step 143. At step 143, the value of the counter i is increased by 1.
Next, at step 144, the condition of i less than n (end condition) is judged, and if true, the procedure returns to step 141 and repeats the detection of an error position, and if false, it proceeds to step 145. At step 145, the stored contents of the memory A are outputted as the error position.
By using a flowchart of FIG. 6, a method of correcting an error of the received word R from the error evaluator polynomial xcfx89(x), the error locator polynomial "sgr"(x), and the detected error position i will be described.
First, at step 150, the counter i is initialized to 0. Then, at step 151, the condition of ixcex5A is judged, and if true, the value of the counter i indicates the error position, and the procedure proceeds to step 152, and if false, the value of the counter i is not the error position, and the procedure proceeds to step 154.
At step 152, by using the error evaluator polynomial xcfx89(x), the differential "sgr"xe2x80x2(x) of the error locator polynomial "sgr"(x), and the error position i, an error value ei is calculated as expressed by equation (16), and the procedure proceeds to step 153. At step 153, the i-th element Cpi of a presumed code word Cp is calculated as Rixe2x88x92ei, and the procedure proceeds to step 155. At step 154, the i-th element Cpi of the presumed code word Cp is made Ri, and the procedure proceeds to step 155.
[Numerical Expression 12]                              e          i                =                              (                          -                              α                i                                      )                    ⁢                                    ω              ⁢                              xe2x80x83                            ⁢                              (                                  α                                      -                    i                                                  )                                                                    σ                xe2x80x2                            ⁡                              (                                  α                                      -                    i                                                  )                                                                        (        16        )            
At step 155, the value of the counter i is increased by 1. At step 156, the condition of i less than n (end condition) is judged, and if true, the procedure returns to step 151 and the calculation of an error value is repeated, and if false, it proceeds to step 157. At step 157, the presumed code word Cp=(Cp0, Cp1. . . , Cpnxe2x88x921) is obtained, and at step 158, the presumed information Ip=(Cp0, Cp1. . . , Cpkxe2x88x921) is obtained from the presumed code word Cp and is outputted.
FIG. 7 shows a structure of a decoding apparatus 160 for performing the foregoing decoding method of the Reed-Solomon code.
This decoding apparatus 160 includes an input terminal 161 to which the received word (input data) R is inputted, and an input terminal 162 to which the erasure flag F corresponding to the received word R is inputted.
Besides, the decoding apparatus 160 includes a syndrome polynomial calculating circuit 163 (see the step 102 of FIG. 2) for obtaining the syndrome polynomial S(x) from the received word R, an erasure position polynomial calculating circuit 164 (see the step 101 of FIG. 2) for obtaining the erasure position polynomial E(x) from the erasure flag F, and an erasure number calculating circuit 165 (see the step 101 of FIG. 2) for obtaining the number xcex5 of erasures from the erasure flag F.
Besides, the decoding apparatus 160 includes an error polynomial calculating circuit 166 (see the step 104 of FIG. 2) which obtains the modified syndrome polynomial Sm(x) from the syndrome polynomial S(x) and the erasure position polynomial E(x), and obtains the error evaluator polynomial xcfx89(x) and the error locator polynomial "sgr"(x) from this modified syndrome polynomial Sm(x).
Besides, the decoding apparatus 160 includes an error value calculating circuit 167 (see the step 152 of FIG. 6) for obtaining the error value ei of each element Ri of the received word R from the error evaluator polynomial xcfx89(x) and the error locator polynomial "sgr"(x), a received word delay circuit 168 for matching the timing of each element Ri of the received word R with the timing of the error value ei outputted from the error value calculating circuit 167, and a subtracter 169 (see the step 153 of FIG. 6) for subtracting the error value ei from each element Ri of the received word R.
Besides, the decoding apparatus 160 includes a signal selecting circuit 170 for selectively taking out either one of the output Rixe2x88x92ei of the subtracter 169 and the output Ri of the received word delay circuit 168, an error position judging circuit 171 which not only detects the error position i from the error locator polynomial "sgr"(x) and outputs a selection signal SEL corresponding to the error position i, but also judges the condition of #roots=deg "sgr"(x) (see the step 108 of FIG. 2), and outputs an error signal ER if false, and an output terminal 172 for extracting the output of the signal selecting circuit 170.
Here, the selection signal SEL outputted from the error position judging circuit 171 is supplied to the signal selecting circuit 170. At the signal selecting circuit 170, the output Rixe2x88x92ei of the subtracter 169 is taken out at the error position i, and the output Ri of the received word delay circuit 168 is taken out at a position which is not the error position i.
Besides, the decoding apparatus 160 includes an error judging circuit 173 which judges the condition of deg xcfx89(x) less than deg "sgr"(x) and the condition of equation (9) (see the steps 105 and 106 of FIG. 2), and outputs an error signal ER if false, an OR gate 174 to which the error signal ER outputted from the error position judging circuit 171 and the error signal ER outputted from the error judging circuit 173 are inputted, and an output terminal 175 for extracting the output of the OR gate 174.
Incidentally, the output of the OR gate 174 is supplied to the signal selecting circuit 170, and in the case that the error signal ER is obtained as the output of the OR gate 174, at the signal selecting circuit 170, the output Ri of the received word delay circuit 168 is always taken out irrespective of the state of the selecting signal SEL.
The operation of the decoding apparatus 160 shown in FIG. 7 will be described.
The received word R (input data) inputted to the input terminal 161 is supplied to the syndrome polynomial calculating circuit 163. In this calculating circuit 163, the syndrome S is calculated from the received word R, and the syndrome polynomial S(x) is obtained. On the other hand, the erasure flag F inputted to the input terminal 162 is supplied to the erasure position polynomial calculating circuit 164. In this calculating circuit 164, the erasure position polynomial E(x) is obtained from the erasure flag F. Besides, the erasure flag F inputted to the input terminal 162 is supplied to the erasure number calculating circuit 165. In this calculating circuit 165, the number xcex5 of erasures is obtained from the erasure flag F.
The syndrome polynomial S(x) obtained in the calculating circuit 163 and the erasure position polynomial E(x) obtained in the calculating circuit 164 are supplied to the error polynomial calculating circuit 166. In this calculating circuit 166, the modified syndrome polynomial Sm(x) is obtained from the syndrome polynomial S(x) and the erasure position polynomial E(x), and further, the error evaluator polynomial xcfx89(x) and the error locator polynomial "sgr"(x) are obtained from this modified syndrome polynomial Sm(x).
The error evaluator polynomial xcfx89(x) and the error locator polynomial "sgr"(x) obtained in the calculating circuit 166 are supplied to the error value calculating circuit 167. In this calculating circuit 167, the error value ei of each element Ri of the received word R is sequentially obtained from the error evaluator polynomial xcfx89(x) and the error locator polynomial "sgr"(x). This error value ei is supplied to the subtracter 169, and is subtracted from each element Ri of the received word R outputted from the received word delay circuit 168.
The error locator polynomial "sgr"(x) obtained in the calculating circuit 166 is supplied to the error position judging circuit 171. In this error position judging circuit 171, the error position i is detected from the error locator polynomial "sgr"(x), and the selection signal SEL corresponding to the error position i is outputted. This selection signal SEL is supplied to the signal selecting circuit 170 as a control signal. In the signal selecting circuit 170, the output Rixe2x88x92ei of the subtracter 169 is taken out at the error position i, and the output Ri of the received word delay circuit 168 is taken out at a position which is not the error position i.
By this, the presumed code word Cp which has been subjected to error correction is taken out from the signal selecting circuit 170, and this presumed code word Cp is extracted to the output terminal 172 as output data. By removing the parity symbol portion from the presumed code word Cp, the presumed information Ip=(Cp0, Cp1, . . . , Cpkxe2x88x921) is obtained.
Incidentally, in the case where the error signal ER is outputted from the error judging circuit 173 or the error position judging circuit 171, this error signal ER is extracted to the output terminal 175, and this error signal ER is supplied to the signal selecting circuit 170. In the signal selecting circuit 170, irrespective of the state of the selection signal SEL, the output Ri of the received word delay circuit 168 is always taken out. By this, in the state where the error signal ER is extracted to the output terminal 175, the received word R is not subjected to error correction but is outputted as it is to the output terminal 172.
As described above, the normal Reed-Solomon code has been capable of being subjected to a mixed correction at one path. On the other hand, with respect to the one-extended Reed-Solomon code, although a method of mixed correction at two paths has been proposed (Richard E. Blahut, xe2x80x9cTHEORY AND PRACTICE OF ERROR CONTROL CODESxe2x80x9d, ISBN: 0-201-10102-5, p. 260xe2x80x94xe2x80x9c9.3 DECODING OF EXTENDED REED-SOLOMON CODESxe2x80x9d), a method of mixed correction at one path has not been proposed. The mixed correction at two paths for the one-extended Reed-Solomon code has disadvantages that it takes a time to perform decoding, and the scale of hardware becomes large.
An object of the present invention is therefore to provide a decoding system for an error correction code, which enable a mixed correction at one path for a one-extended Reed-Solomon code.
A decoding method for an error correction code of the present invention comprises the steps of obtaining a syndrome polynomial from input data containing an extended symbol through calculation inclusive of the extended symbol; obtaining an erasure position polynomial from an erasure flag corresponding to the input data; obtaining the number of erasures from the erasure flag corresponding to the input data; obtaining an error locator polynomial and an error evaluator polynomial from the syndrome polynomial and the erasure position polynomial; obtaining an error position from the error locator polynomial and the error evaluator polynomial; obtaining an error value containing the extended symbolfrom the error locator polynomial and the error evaluator polynomial; obtaining output data by correcting an error of the input data by using the error position and the error value; and performing correctable judgement inclusive of correctable judgement of the extended symbol.
In the present invention, since means for performing a normal correction and an erasure correction of an extended symbol is integrated, a mixed correction at one path for, for example, the one-extended Reed-Solomon code becomes possible.